<h1>Chipmunk Game Dynamics</h1>


	<h2>Introduction</h2>


	<p>First of all, Chipmunk is a 2D rigid body physics library distributed under the <span class="caps">MIT</span> license. Though not yet complete, it is intended to be fast, numerically stable, and easy to use.</p>


	<p>It&#8217;s been a long time in coming, but I&#8217;ve finally made a stable and usable physics implementation. While not feature complete yet, it&#8217;s well on it&#8217;s way. This is thanks mostly to Erin Catto&#8217;s contact persistence idea (<a href="http://www.gphysics.com/downloads/">link</a>). It allows for stable stacks of objects with very few iterations of the contact solution.</p>


	<h2><span class="caps">API</span></h2>


	<h3>Initializing Chipmunk</h3>


	<p>Initializing Chipmunk is an extremely complicated process. The following code snippet steps you through the process:</p>


<pre><code>
    cpInitChipmunk(); /* Actually, that's pretty much it */
</code></pre>

	<h3>Chipmunk memory management</h3>


For many of the structures you will use, Chipmunk uses a standard set of memory management functions. For instance:
	<ul>
	<li><code>cpSpaceAlloc()</code> allocates but does not initialize a <code>cpSpace</code> struct.</li>
		<li><code>cpSpaceInit(space, other_args)</code> initializes a <code>cpSpace</code> struct.</li>
		<li><code>cpSpaceNew(args)</code> allocates and initializes a <code>cpSpace</code> struct using <code>args</code>.</li>
		<li><code>cpSpaceDestroy(space)</code> frees all dependancies, but does not free the <code>cpSpace</code> struct.</li>
		<li><code>cpSpaceFree(space)</code> frees all dependancies and the <code>cpSpace</code> struct.</li>
	</ul>


	<p>While you will probably always use the new/free versions, the others can be helpful when writing language extensions.</p>


	<p>In general, you are responsible for freeing any structs that you allocate. The only exception is that <code>cpShapeDestroy()</code> also destroys the specific shape struct that was passed to the constructor.</p>


	<h3>Chipmunk vectors: <code>cpVect</code></h3>


<pre><code>
    typedef struct cpVect{
        float x,y;
    } cpVect
</code></pre>

	<p>Simply a 2D vector packed into a struct. May change in the future to take advantage of Altivec/SSE.</p>


<pre><code>
    #define cpvzero ((cpVect){0.0f, 0.0f})
</code></pre>

	<p>Constant for the zero vector.</p>


<pre><code>
    cpVect cpv(const float x, const float y)
</code></pre>

	<p>Convenience constructor for creating new <code>cpVect</code> structs.</p>


<pre><code>
    cpVect cpvadd(const cpVect v1, const cpVect v2)
    cpVect cpvsub(const cpVect v1, const cpVect v2)
</code></pre>

	<p>Add or subtract two vectors.</p>


<pre><code>
    cpVect cpvneg(const cpVect v)
</code></pre>

	<p>Negate a vector.</p>


<pre><code>
    cpVect cpvmult(const cpVect v, const float s)
</code></pre>

	<p>Scalar multiplication.</p>


<pre><code>
    float cpvdot(const cpVect v1, const cpVect v2)
</code></pre>

	<p>Vector dot product.</p>


<pre><code>
    float cpvcross(const cpVect v1, const cpVect v2)
</code></pre>

	<p>2D vector cross product analog. The cross product of 2D vectors exists only in the z component, so only that value is returned.</p>


<pre><code>
    cpVect cpvperp(const cpVect v)
</code></pre>

	<p>Returns the perpendicular vector. (90 degree rotation)</p>


<pre><code>
    cpVect cpvproject(const cpVect v1, const cpVect v2)
</code></pre>

	<p>Returns the vector projection of <code>v1</code> onto <code>v2</code>.</p>


<pre><code>
    cpVect cpvrotate(const cpVect v1, const cpVect v2)
</code></pre>

	<p>Uses complex multiplication to rotate (and scale) <code>v1</code> by <code>v2</code>.</p>


<pre><code>
    cpVect cpvunrotate(const cpVect v1, const cpVect v2)
</code></pre>

	<p>Inverse of <code>cpvrotate()</code>.</p>


<pre><code>
    float cpvlength(const cpVect v)
</code></pre>

	<p>Returns the length of <code>v</code>.</p>


<pre><code>
    float cpvlengthsq(const cpVect v)
</code></pre>

	<p>Returns the squared length of <code>v</code>. Faster than <code>cpvlength()</code> when you only need to compare lengths.</p>


<pre><code>
    cpVect cpvnormalize(const cpVect v)
</code></pre>

	<p>Returns a normalized copy of <code>v</code>.</p>


<pre><code>
    cpVect cpvforangle(const float a)
</code></pre>

	<p>Returns the unit length vector for the given angle (in radians).</p>


<pre><code>
    float cpvtoangle(const cpVect v)
</code></pre>

	<p>Returns the angular direction <code>v</code> is pointing in (in radians).</p>


<pre><code>
    *cpvstr(const cpVect v)
</code></pre>

	<p>Returns a string representation of <code>v</code>. <strong><span class="caps">NOTE</span>:</strong> The string points to a static local and is reset every time the function is called.</p>


	<h3>Chipmunk bounding boxes: <code>cpBB</code></h3>


<pre><code>
    typedef struct cpBB{
        float l, b, r ,t;
    } cpBB
</code></pre>

	<p>Simple bounding box struct. Stored as left, bottom, right, top values.</p>


<pre><code>
    cpBB cpBBNew(const float l, const float b, const float r, const float t)
</code></pre>

	<p>Convenience constructor for <code>cpBB</code> structs.</p>


<pre><code>
    int cpBBintersects(const cpBB a, const cpBB b)
</code></pre>

	<p>Returns true if the bounding boxes intersect.</p>


<pre><code>
    int cpBBcontainsBB(const cpBB bb, const cpBB other)
</code></pre>

	<p>Returns true if <code>bb</code> completely contains <code>other</code>.</p>


<pre><code>
    int cpBBcontainsVect(const cpBB bb, const cpVect v)
</code></pre>

	<p>Returns true if <code>bb</code> contains <code>v</code>.</p>


<pre><code>
    cpVect cpBBClampVect(const cpBB bb, const cpVect v)
</code></pre>

	<p>Returns a copy of <code>v</code> clamped to the bounding box.</p>


<pre><code>
    cpVect cpBBWrapVect(const cpBB bb, const cpVect v)
</code></pre>

	<p>Returns a copy of <code>v</code> wrapped to the bounding box.</p>


	<h3>Chipmunk spatial hashes: <code>cpSpaceHash</code></h3>


	<p><em>The spatial hash isn&#8217;t yet ready for user use. However, it has been made in a generic manner that would allow it to be used for more than just Chipmunk&#8217;s collision detection.</em></p>


	<h3>Chipmunk rigid bodies: <code>cpBody</code></h3>


<pre><code>
    typedef struct cpBody{
        float m, m_inv;
        float i, i_inv;

        cpVect p, v, f;
        float a, w, t;
        cpVect rot;
    } cpBody
</code></pre>

	<ul>
	<li><code>m</code>, and <code>m_inv</code> are the mass and its inverse.</li>
		<li><code>i</code>, and <code>i_inv</code> are the moment of inertia and its inverse.</li>
		<li><code>p</code>, <code>v</code>, and <code>f</code> are the position, velocity and force respectively.</li>
		<li><code>a</code>, <code>w</code>, and <code>t</code> are the angle (in radians), angular velocity (rad/sec), and torque respectively.</li>
		<li><code>rot</code> is the rotation of the body as a unit length vector. (can be used with <code>cpvrotate()</code>)</li>
	</ul>


<pre><code>
    cpBody *cpBodyAlloc(void)
    cpBody *cpBodyInit(cpBody *body, float m, float i)
    cpBody *cpBodyNew(float m, float i)

    void cpBodyDestroy(cpBody *body)
    void cpBodyFree(cpBody *body)
</code></pre>

	<p>Uses the standard suite of Chipmunk memory functions. <code>m</code> and <code>i</code> are the mass and moment of inertia for the body.</p>


<pre><code>
    void cpBodySetMass(cpBody *body, float m);
    void cpBodySetMoment(cpBody *body, float i);
    void cpBodySetAngle(cpBody *body, float a);
</code></pre>

	<p>Because several of the values are linked, (m/m_inv, i/i_inv, a/rot) don&#8217;t set them explicitly, use these setter functions instead.</p>


	<p><strong><span class="caps">NOTE TO SELF</span>:</strong> <em>Need to write force/impulse application helpers.</em></p>


<pre><code>
    void cpBodyUpdateVelocity(cpBody *body, cpVect gravity, float damping, float dt)
</code></pre>

	<p>Updates the velocity of the body using Euler integration. You don&#8217;t need to call this unless you are managing the object manually instead of adding it to a <code>cpSpace</code>.</p>


<pre><code>
    void cpBodyUpdatePosition(cpBody *body, float dt)
</code></pre>

	<p>Updates the position of the body using Euler integration. Like <code>cpBodyUpdateVelocity()</code> you shouldn&#8217;t need to call this yourself.</p>


<strong>Usage tips:</strong>
	<ul>
	<li>Use forces to modify the rigid bodies if possible. This is likely to be the most stable.</li>
		<li>Modifying a body&#8217;s velocity shouldn&#8217;t necessarily be avoided, but applying large changes can cause strange results in the simulation. Experiment, but be warned.</li>
		<li>Modifying a body&#8217;s position often is a bad idea. Doing so to move an object into place is fine, but don&#8217;t do it every step. Otherwise you&#8217;re likely to get the position/velocity badly out of sync.</li>
	</ul>


	<h3>Chipmunk collision shape: <code>cpShape</code></h3>


<pre><code>
    typedef struct cpShape{
        cpShapeType type;
        union {
            cpCircle *circle;
            cpSegment *segment;
            cpPoly *poly;
            void *ptr;
        } shape;

        unsigned long id;

        cpBB bb;
        int collision_type;
        void *data;

        cpBody *body;
        float e, u;
        cpVect surface_v;
    } cpShape;
</code></pre>

	<ul>
	<li><code>type</code> and the <code>shape</code> union should not be modified by the user.</li>
		<li><code>id</code> is the hash value used by the spatial hash. Shouldn&#8217;t need to be modified by the user.</li>
		<li><code>bb</code> is the bounding box of the shape.</li>
		<li>For an explanation of <code>collision_type</code>, see the collision pair function section below.</li>
		<li><code>data</code> is a user definable field.</li>
		<li><code>body</code> is the rigid body the shape is attached to.</li>
		<li><code>e</code> and <code>u</code> are the elasticity and frictional coefficient respectively.</li>
		<li><code>surface_v</code> is the surface velocity of the object. Useful for creating conveyor belts or players that move around. This value is only used when calculating friction, not the collision.</li>
	</ul>


<pre><code>
    cpShape *cpShapeAlloc(void)
    cpShape *cpShapeInit(cpShape *shape, cpShapeType type, void *shape_obj, cpBody *body)
    cpShape *cpShapeNew(cpShapeType type, void *shape_obj, cpBody *body)

    void cpShapeDestroy(cpShape *shape)
    void cpShapeFree(cpShape *shape)
</code></pre>

	<p>Another set of standard Chipmunk memory functions. <code>type</code> is the shape type, <code>shape_obj</code> is one of the 3 types of shape structs, <code>body</code> is the rigid body you want to associate the collision shape with.</p>


	<p>There are currently 3 possible collision shapes: circles, line segments, and convex polygons. All three collision shapes are encapsulated by a <code>cpShape</code> struct. This means that creating a collision shape is a two part process, instantiating a specific shape struct and also a generic <code>cpShape</code> struct to hold it. Additionally, you may want to set other properties such as the elasticity of the shape.</p>


	<p>A typical shape instantiation is as follows:</p>


<pre><code>
    cpShape *shape = cpShapeNew(CP_CIRCLE_SHAPE, cpCircleNew(cpvzero, radius), body);
    shape-&gt;e = 0.0;
</code></pre>

	<p>Additionally, there is <code>CP_SEGMENT_SHAPE</code> that you would use with a <code>cpSegment</code>, and <code>CP_POLY_SHAPE</code> that you would use with a <code>cpPoly</code>.</p>


	<p><strong><span class="caps">NOTE</span>:</strong> <em>line segments are intended mostly as a static shape and are not able to collide with other line segments.</em></p>


<pre><code>
    cpBB cpShapeCacheBB(cpShape *shape)
</code></pre>

	<p>Updates and returns the bounding box of <code>shape</code>.</p>


<pre><code>
    void cpResetShapeIdCounter(void)
</code></pre>

	<p>Chipmunk keeps a counter so that every new shape is given a unique hash value to be used in the spatial hash. Because this affects the order in which the collisions are considered it could cause another simulation constructed in the exact same way to give a different result. Reseting the counter every time you create a new space and add shapes to it will guarantee the same collision ordering.</p>


	<p><strong><span class="caps">NOTE</span>:</strong> <em>Because rigid bodies are not tied to specific collision shapes, you can attach as many as you want. This allows you to create composite collision shapes that should be able to fill just about any need.</em></p>


	<h3>Chipmunk collision shape structures: <code>cpCircle</code>, <code>cpSegment</code>, and <code>cpPoly</code></h3>


	<p>The only thing you should ever have to do with an of the specific shape structures is create them, they are destroyed along with their associated <code>cpShape</code> struct when <code>cpShapeDestroy()</code> is called. While you can read the fields of the structures if you wish, they are not intended to be modified at runtime.</p>


<pre><code>
    cpCircle *cpCircleNew(cpVect offset, float radius)
</code></pre>

	<p>The simplest and fastest of the collision shapes. <code>center</code> is the offset from the rigid body&#8217;s center, and <code>radius</code> is the radius.</p>


<pre><code>
    cpSegment* cpSegmentNew(cpVect a, cpVect b)
</code></pre>

	<p>While segments can be attached to moving bodies, they are unable to collide with other segments. <code>a</code> and <code>b</code> are the endpoints of the segment.</p>


<pre><code>
    cpPoly *cpPolyNew(int numVerts, cpVect *verts, cpVect offset)
</code></pre>

	<p>The most complicated collision type. <code>numVerts</code> is simply the number of vertexes in the poly, <code>verts</code> is an array of <code>cpVect</code> structs, and <code>offset</code> is the offset from the rigid body&#8217;s center of gravity. <code>verts</code> <strong>must</strong> describe a convex polygon with a counterclockwise winding, otherwise you will get really odd results.</p>


	<p><strong><span class="caps">NOTE</span>:</strong> <em>These structs contain instance specific transformation information and cannot be shared by more than one <code>cpShape</code>.</em></p>


	<h3>Chipmunk spaces: <code>cpSpace</code></h3>


<pre><code>
    cpSpace* cpSpaceAlloc(void)
    cpSpace* cpSpaceInit(cpSpace *space, int iterations)
    cpSpace* cpSpaceNew(int iterations)

    void cpSpaceDestroy(cpSpace *space)
    void cpSpaceFree(cpSpace *space)

</code></pre>

	<p>More standard Chipmunk memory functions. <code>iterations</code> is the number of iterations that should be used when resolving collisions. 10 iterations is probably a good starting number, but dense simulations will probably need more.</p>


<pre><code>
        void cpSpaceFreeShapesAndBodies(cpSpace *space)
</code></pre>

	<p>This will free all of the shapes and bodies that have been added to <code>space</code>.</p>


<pre><code>
    void cpSpaceAddShape(cpSpace *space, cpShape *shape)
    void cpSpaceAddStaticShape(cpSpace *space, cpShape *shape)
    void cpSpaceAddBody(cpSpace *space, cpBody *body)

    void cpSpaceRemoveShape(cpSpace *space, cpShape *shape)
    void cpSpaceRemoveStaticShape(cpSpace *space, cpShape *shape)
    void cpSpaceRemoveBody(cpSpace *space, cpBody *body)
</code></pre>

	<p>Use these to add and remove shapes and bodies from the space. Static shapes are not rehashed when the space is updated, so they should not move.</p>


<pre><code>
    void cpSpaceResizeStaticHash(cpSpace *space, float dim, int count)
    void cpSpaceResizeActiveHash(cpSpace *space, float dim, int count)
</code></pre>

	<p>Spatial hashes are fairly size sensitive. You should set <code>dim</code> to be the average object size. <code>count</code> is the minimum number of slots in the hash table.</p>


<pre><code>
    void cpSpaceRehashStatic(cpSpace *space)
</code></pre>

	<p>Rehashes the shapes in the static spatial hash. You need to do this every time you change the position of one of the static shapes.</p>


<pre><code>
    void cpSpaceStep(cpSpace *space, float dt)
</code></pre>

	<p>Update the space for the give time step. Using a fixed time step will increase the efficiency of the contact persistence, requiring fewer iterations to resolve the collisions.</p>


	<h2>Collision pair functions</h2>


	<p>It would be useful to know when two specific kinds of shapes collide. For instance, a player shape, and a bullet shape.</p>


<pre><code>
    typedef int (*cpCollFunc)(cpShape *a, cpShape *b, cpContact *contacts, int numContacts, void *data)
</code></pre>

	<p>Prototype for a collision callback function. The two colliding shapes are passed as <code>a</code> and <code>b</code>, along with the contact points, and a user definable pointer are passed as arguments.</p>


<pre><code>
    void cpSpaceAddCollisionPairFunc(cpSpace *space, unsigned long a, unsigned long b, cpCollFunc func, void *data)
</code></pre>

	<p>Register <code>func</code> to be called when a collision is found between a shapes with <code>collision_type</code> fields that match <code>a</code> and <code>b</code>. <code>data</code> is passed to <code>func</code> as a parameter. The ordering of the collision types will match the ordering passed to the callback function.</p>


	<p>Passing <code>NULL</code> for <code>func</code> will reject any collision with the given collision type pair.</p>


<pre><code>
    void cpSpaceRemoveCollisionPairFunc(cpSpace *space, unsigned long a, unsigned long b)
</code></pre>

	<p>Remove the function for the given collision type pair.</p>


	<h2>Pitfalls</h2>


These are, off the top of my head, some problems you might run into:
	<ul>
	<li>Bugs. I&#8217;d be surprised if there are none.</li>
		<li>Memory leaks. As far as I know, there aren&#8217;t any significant leaks though. </li>
		<li>There is no swept volume collisions. Fast moving objects might pass right through one another.</li>
		<li>Pointy or thin polygons aren&#8217;t handled well. Collision points are generated at the poly&#8217;s vertexes. I haven&#8217;t decided what to do about this yet.</li>
		<li>Joints are not implemented yet so there is no easy way of joining objects together.</li>
		<li>Future <span class="caps">API</span> changes. Documented functions might disappear, undocumented functions are likely to disappear.</li>
		<li>Elastic shapes will not stack well.</li>
	</ul>


	<h2>Performance/Quality tuning</h2>


There are a number of things you can do to increase the performance of Chipmunk.
	<ul>
	<li>Use simpler collision shapes when possible. It&#8217;s easier on the collision detection, you&#8217;ll generate fewer contact points, and require fewer iterations.</li>
		<li>Make sure you have your spatial hashes tuned properly. It may take some experiment to find the optimal dim/count parameters.</li>
		<li>Use fewer iterations.</li>
		<li>Use a larger time step.</li>
		<li>Use a fixed time step. This allows contact persistence to work properly, and allows you to use an order of magnitude fewer iterations.</li>
	</ul>


If you have problems with jittery or vibrating objects, you need to do mostly the opposite. 
	<ul>
	<li>Use simpler shapes.Simpler shapes generate fewer contact which increase the efficiency of each iteration.</li>
		<li>Use more iterations.</li>
		<li>Use a smaller time step.</li>
		<li>Use a fixed time step. Same reason as above.</li>
	</ul>


	<h2><span class="caps">TODO</span></h2>


There are a number of things left on my todo list:
	<ul>
	<li>Joints of all kinds.</li>
		<li>Post collision queries. Being able to query for all the impulses that were applied to an object would be useful.</li>
		<li>Python binding. (possibly others if I can get help)</li>
	</ul>


	<h2>License</h2>


	<p>Copyright&#169; 2007 Scott Lembcke</p>


	<p>Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the &#8220;Software&#8221;), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:</p>


	<p>The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.</p>


	<p><span class="caps">THE SOFTWARE IS PROVIDED</span> &#8220;AS IS&#8221;, <span class="caps">WITHOUT WARRANTY OF ANY KIND</span>, EXPRESS <span class="caps">OR IMPLIED</span>, INCLUDING <span class="caps">BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY</span>, FITNESS <span class="caps">FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT</span>. IN <span class="caps">NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM</span>, DAMAGES <span class="caps">OR OTHER LIABILITY</span>, WHETHER <span class="caps">IN AN ACTION OF CONTRACT</span>, TORT <span class="caps">OR OTHERWISE</span>, ARISING <span class="caps">FROM</span>, OUT <span class="caps">OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE</span>.</p>
